package cn.dapeng.sort;

import cn.dapeng.utils.BuilderArray;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.sort
 * @Description 堆排序
 * @ClassName HeapSort
 * @Author xupenghong
 * @Date 2024/9/3 14:16
 * @Version 1.0.0
 *
 * 时间复杂度 O(N*logN)
 */
public class HeapSort {


    /**
     * 上浮操作
     *
     * @param array : 已构建出来的大根堆
     * @param index : 当前要上浮的节点的索引
     *
     * 时间复杂度 O(N*logN)
     */
    public static void heapInsert(int[] array, int index) {
        while (array[index] > array[(index - 1) / 2]) {
            BuilderArray.swap(array, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 从index位置，向下看，不断下沉
     * 停：较大的孩子都不再比index位置的数大;已经没孩子了
     *
     * @param array    : 已构建出来的大根堆
     * @param index    : 当前要上浮的节点的索引
     * @param heapSize : 堆大小， 也就是数组的前N个元素
     *
     * 时间复杂度 O(N*logN)
     */
    public static void heapify(int[] array, int index, int heapSize) {
        int left = index * 2 + 1;

        while (left < heapSize) {
            // 计算左右两个节点谁大，大的与父节点交换位置
            // 如果有右节点， 并且右节点大于左节点，那么右节点是最大的，否则左节点大
            int largest = (left + 1) < heapSize && (array[left + 1] > array[left]) ? left + 1 : left;
            // 左右子节点中最大的与父节点做比较， 计算出最大的节点
            largest = array[largest] > array[index] ? largest : index;
            //如果最大的节点是父节点，退出循环
            if (largest == index) break;

            BuilderArray.swap(array, index, largest);
            index = largest;
            left = index * 2 + 1;
        }

    }

    /**
     * 1. 构建大根堆
     * 2. 把大根堆的第一个元素与最后一个元素交换，然后在重新构建大根堆
     *
     * 也就是把0位置与N-1位置元素交换， N-1肯定是当前数组[0~N-1]的最大元素，然后重新构建0 到 N-2位置成大根堆
     *      把0位置与N-2位置元素交换，N-2肯定是当前数组[0~N-2]的最大元素，然后重新构建0 到 N-3位置成大根堆
     *      循环直到待排序的数组长度为0，整个数组就是一个从小到大排好序的数组
     *
     *
     * @param array
     */
    public static void sort(int[] array) {
        if (array == null || array.length < 2) return;

        // 1. 把一个数组调整成大根堆 第一张方式 时间复杂度 时间复杂度 O(N*logN)
//        for (int i = 1; i < array.length; i++) {
//            heapInsert(array, i);
//        }

        // 2. 把一个数组调成大根堆，第二种方式 时间复杂度 时间复杂度 O(N)
        for (int i = array.length - 1; i >= 0; i--) {
            heapify(array, i, array.length);
        }

        for (int i = array.length - 1; i >= 0; i--) {
            BuilderArray.swap(array, 0, i);
            heapify(array, 0, i);
        }
    }

    /**
     * 如果一个大根堆突然某个位置的数值变了，那么如何再把这个数组处理成大根堆
     * 在那个位置做一次heapInsert和heapify操作即可
     */
}
